package org.aplombh.java.awcing.basic.struct.trie;

import java.util.Scanner;

/**
 * 维护一个字符串集合，支持两种操作：
 * <p>
 * I x 向集合中插入一个字符串 x；
 * Q x 询问一个字符串在集合中出现了多少次。
 * 共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
 * <p>
 * 输入格式
 * 第一行包含整数 N，表示操作数。
 * <p>
 * 接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
 * <p>
 * 输出格式
 * 对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
 * <p>
 * 每个结果占一行。
 * <p>
 * 数据范围
 * 1≤N≤2∗104
 * 输入样例：
 * 5
 * I abc
 * Q abc
 * Q ab
 * I ab
 * Q ab
 * 输出样例：
 * 1
 * 0
 * 1
 */
// 并查集
public class TrieString_835 {

    public static void main(String[] args) {

        TrieString trieString = new TrieString();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        while (n-- != 0) {

            String op = scanner.next();
            String string = scanner.next();

            if (op.charAt(0) == 'I') {
                trieString.insert(string);
            } else {
                System.out.println(trieString.query(string));
            }
        }
    }
}

class TrieString {
    public static final int N = 100010;
    private final int[][] son;
    private final int[] cnt;
    private int idx;

    public TrieString() {
        son = new int[N][26];
        cnt = new int[N];
    }

    void insert(String string) {

        char[] str = string.toCharArray();
        int p = 0, u;
        // 将每位字符串分开存储
        for (char c : str) {
            // 将该字符转换为在26个字母中的位置关系
            u = c - 'a';
            // 如果遍历到该位置，该位置没有存储过数据，说明该位置未存储过数据，为一个新的起始字符串
            if (son[p][u] == 0) son[p][u] = ++idx;
            // 将p指向该点的下一个节点
            p = son[p][u];
        }
        // cnt存储以该节点为尾节点的所有结点的个数
        cnt[p]++;
    }

    int query(String string) {

        char[] str = string.toCharArray();
        int p = 0, u;
        // 查询时将每位字符分开匹配
        for (char c : str) {
            u = c - 'a';
            // 如果遍历到字符串的某字符无记录，则该字符串未存储过，直接返回
            if (son[p][u] == 0) return 0;
            // 将p指向该点的下一个节点
            p = son[p][u];
        }
        // 返回该节点为尾节点的字符串的个数（idx保证不重复）
        return cnt[p];
    }

    void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 26; j++) {
                System.out.print(son[i][j] + " ");
            }
            System.out.println();
        }
    }
}